#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // vector<int> dailyTemperatures(vector<int> &temperatures)
    // {
    //     int length = temperatures.size();
    //     vector<int> nums(length, 0);
    //     for (int i = 0; i < length; i++)
    //     {
    //         for (int j = i + 1; j < length; j++)
    //         {
    //             if (temperatures[j] > temperatures[i])
    //             {
    //                 nums[i] = j - i;
    //                 break;
    //             }
    //         }
    //     }
    //     return nums;
    // }

    vector<int> dailyTemperatures(vector<int> &temperatures)
    {
        int length=temperatures.size();
        vector<int> result(length,0);
        stack<int> stk;
        stk.push(0);
        for(int i=1;i<length;i++)
        {
            while(!stk.empty() && temperatures[i]>temperatures[stk.top()])
            {
                result[stk.top()]=i-stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return result;
    }
};

int main()
{
    vector<int> temperature{73, 74, 75, 71, 69, 72, 76, 73};
    Solution sol;
    vector<int> nums = sol.dailyTemperatures(temperature);
    for (auto num : nums)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}